1. Field of the Invention
This invention relates to mechanisms for protecting software against unauthorized use, in particular against unauthorized copying.
2. Description of the Related Art
The Business Software Alliance estimates the 1995 financial losses attributed to software piracy as US$ 8.1 Billion for business application software and US$ 15.2 Billion for all software.
Solutions have been proposed in two areas:
improved Intellectual Property Rights (IPR) legislation, and
enhanced electronic copy protection (ECP) mechanisms.
IPR legislation and enforcement are improving in many countries, but there are still significant difficulties in other parts of the world. As a result, some vendors are currently reassessing ECP.
Some example requirements that an ECP mechanism may potentially satisfy are listed below:
Unauthorized users or customers should be prohibited from executing protected software.
The customer should not be prohibited from making backups.
The ECP mechanism should have minimal impact upon the user interface. The visible impact should be limited to the first initial login to the operating system and/or smart card.
Only standard hardware and software assumptions should be made. For example, although hardware dongles provide copy protection services, many vendors do not wish to limit the sale of the software to the collection of customers who own or are willing to install a dongle.
The ECP mechanism should not limit execution of the protected software to a limited collection of machines. When a customer legitimately purchases software, the customer should be able to execute the software on any machine regardless of ownership. The customer should optionally be able to authorize simultaneous execution of the software in multiple machines.
The ECP mechanism should have no required network dependencies in order to execute an already purchased protected program.
The vendor should be permitted to distribute an identical version of the protected software to all customers. This requirement permits the protected software to be distributed through normal channels such as, for example, CD-ROMS, floppy disks, or network bulletin boards.
It should be excessively difficult and/or computationally infeasible for a potential software pirate to circumvent the ECP mechanism without modifying the protected program. This requirement serves as a virus-protection measure because a digital signature supplied by the vendor would not validate if a pirate distributes a modified version of the original program.
The ECP mechanism should not disclose the private keying material to the vendor, to any program produced by the vendor, or to any potential Trojan horse program. Though the primary functionality is to protect the software vendor, one must not do so at the expense of the customer.
The ECP mechanism should be available in a software-only version as well as in a hardware-assisted version, using a smart card, for example, to assure widespread market acceptance.
In the publication by Choudhury, et al., xe2x80x9cCopyright Protection for Electronic Publishing over Computer Networksxe2x80x9d, a mechanism is proposed in which a protected document can be viewed only via a specially configured viewer program, which allows a customer to view the document only if the customer supplies to the viewer the customer""s private keying material. This deters the customer from distributing unauthorized copies of the viewer program, since that would require the customer to divulge his or her private keying material to others. However, because this mechanism requires that the viewer program obtain access to the private keying material, it breaks one of the requirements described above. Furthermore, this mechanism may not be used in conjunction with a smart card that is configured to avoid releasing private keying material.
An overview on asymmetric cryptography, for example on the RSA (Rivest-Shamir-Adleman) scheme, and probabilistic encryption, for example the Blum-Goldwasser probabilistic public-key encryption scheme, can be found in the Menezes et al., book xe2x80x9cHandbook of Applied Cryptography.xe2x80x9d
The Chi-Square Test, the Kolmogorov-Smimov Test, and the Serial Correlation Test are described in the publication by Knuth, xe2x80x9cThe Art of Computer Programming.xe2x80x9d
An overview over different probabilistic proof schemes, for example zero knowledge proof schemes (e.g. Feige-Fiat-Shamir scheme, Guillou-Quisquater scheme, Blum-Feldmann-Micali scheme, Brassard scheme, Crepau scheme, etc.) or witness hiding proof schemes (e.g. Feige-Shamir scheme, etc.) can be found in the Menezes book.
An overview of digital signature schemes (e.g. Rivest-Shamir-Adleman, etc.,) and a formal mathematical definition of digital signatures can be found in the Menezes book.
An example of a message digest function (otherwise known as a one-way hash function) is MD5 as disclosed by Rivest in xe2x80x9cThe MD5 Message-Digest Algorithmxe2x80x9d. It is computationally infeasible or very difficult to compute the inverse of a message digest.
In the publiction by Fenstermacher et al., cryptographic randomness from air turbulence in disk drives is described.
An object of the present invention is to provide an improved ECP (electronic copy protection) mechanism that is able to satisfy most, if not all of the example requirements described above.
Some important algorithms that are used in the present invention are listed below.
Given n (of an RSA (Rivest-Shamir-Addleman) key pair) and "PHgr", determine the prime factors (p,q) of nEMBEDDED such that n=pxc2x7q and "PHgr"=(pxe2x88x921)(qxe2x88x921):       p    =                            (                      n            -            Φ            +            1                    )                +                                                            (                                  n                  -                  Φ                  +                  1                                )                            2                        -                          4              ·              n                                          2            q    =          n      p      
Given an RSA public key, n,e, and private key, d, compute "PHgr".
* Zn is the set of integers modulo n
* Z*n={X xcex5Zn |gcd(x,n)=I}
* Let exc2x7dxe2x88x921=2st where t is an odd integer
1. Select a random integer, a such that a xcex5Z*n 
2. Compute w=a2sxe2x88x921t 
3. If wxe2x89xa0xc2x11(mod n) go to 1
4. Result: gcd(wxe2x88x921,n) where gcd denotes Greatest Common Divisor
Not every well-known algorithm used by this invention is described herein. Other well-known algorithms, e.g., computing an inverse, and computing the gcd, can be found in the Menezes book.
A chosen-plaintext attack is one where the adversary chooses plaintext and is then given corresponding ciphertext. Subsequently, the adversary uses any information deduced in order to recover plaintext corresponding to previously unseen ciphertext, see Menezes.
An adaptive chosen-plaintext attack is a chosen-plaintext attack wherein the choice of plaintext may depend on the ciphertext received from previous results, again, see Menezes.
A zero knowledge proof protocol resists both chosen-plaintext attacks and adaptive chosen-plaintext attacks.
The present invention makes use of probabilistic proof. A probabilistic proof involves at least two parties, A and B. A possesses private keying material and B has no access to A""s private keying material without disclosing the private keying material itself. A""s proof is probabilistic rather than absolute because B forces A to demonstrate that A probably has access to the private keying material by supplying evidence.
There are two variants of probabilistic proofs:
a) zero-knowledge-proofs, where it is provable that B or any observer of the proof learns nothing from the proof, except the fact that A possesses the private keying material.
b) witness-challenge-response-proofs, which comprise the following four elements in a sequence:
1. A sends information which is not constant for all invocations of the proof to B. This information is called the witness. For many protocols, the witness is generated randomly, and should never be repeated.
2. B sends information to A, called the challenge. For many protocols, the challenge is generated randomly.
3. A sends a response to B.
4. B verifies whether A indeed knows the private keying material by executing computations involving the witness, the challenge, and the response.
In fact, many zero-knowledge-proofs are witness-challenge-response-proofs.
Zero knowledge proof schemes are e.g. the Feige-Fiat-Shamir scheme or the Guillou-Quisquater scheme, but also the Mono-directional zero knowledge proof schemes, e.g. the Blum-Feldmann-Micali scheme, or Statistical zero knowledge proof schemes, e.g. the Brassard scheme or the Crepau scheme, etc.
Witness hiding proof schemes are e.g. the Feige-Shamir scheme, etc.
One should not confuse probabilistic public-key encryption (for, the purpose of providing confidentiality) with probabilistic proofs. In the first case, probabilistic means are used to execute the encryption algorithm. In the second case, probabilistic means are used to define a degree of assurance for a service such as identification.
In the following, one possible general structure of a zero-knowledge protocol is described (cp. Menezes, et al.). For illustrative purposes, this general structure is also of the witness-challenge-response-proof format.
The protocol involves two parties, A and B.
1. The prover claiming to be A selects a random element from a pre-defined set as its secret commitment (providing hidden randomization), and from this computes an associated (public) witness. This provides initial randomness for variation from other protocol runs, and defines a set of questions all of which the prover claims to be able to answer, thereby a priori constraining his or her forthcoming response. Only the legitimate party A, with knowledge of A""s secret, is truly capable of answering all the questions, and the answer to any one of these provides no information about A""s long-term secret.
2. B""s subsequent challenge selects one of these questions.
3. A provides its response.
4. B checks the response for correctness.
The protocol may be iterated to improve the bound which limits the probability of successful cheating.
Each customer may post his or her public keying material to a publicly accessed directory without compromising the corresponding private keying material. The customer usually should guard his or her private keying material as a close secret, as otherwise the cryptographic system may not guarantee correctness. The best known mechanism for protecting one""s private keying material is through the use of a smart card. In this case, the smart card is a device with no interface for releasing private keying material (in a non-cryptographically protected form).
Although smart cards provide the best protection, social factors of electronic commerce may provide a role in ensuring private keying material protection. One of the significant difficulties associated with asymmetric cryptographic services is authentication. For example, if A posts his or her public keying material to a public directory, then how does B assess validity? That is, a pirate may attempt to masquerade as A but post the pirate""s keying material. Some commercial organizations provide solutions to this problem by acting as Certification Authorities (CA). For (possibly) a fee, the CA solicits identifying material from potential customers such as a driver""s license or passport. After validating the identifying material, the CA posts the customer""s public keying material to a public directory, and the CA signs a certificate (using a digital signature with the CA""s private keying material) that holds the customer""s public keying material. Standardized services, for example X.500, may be adopted to help facilitate the use of directories that contain public keying material.
Once a customer posts his or her public keying material to the CA, the customer should make an effort to protect his or her private keying material. In this case, if the customer""s private keying material were to become unknowingly compromised, then the private keying material could no longer be used in a meaningful way.
According to the invention there is provided a computer system comprising a protection mechanism for protecting software, the protection mechanism comprising at least one challenge means associated with a protected item of software, and at least one response means in which private keying material is accessed, wherein:
a) the challenge means has no access to the private keying material,
b) the response means comprises means for proving to the challenge means that the response means has access to the private keying material by interacting with the challenge means using a probabilistic proof scheme, and
c) the challenge means comprises means for prohibiting a customer from using some or all of the items of software unless the challenge means knows that the probabilistic proof is successful.
According to a further aspect of the invention, there is provided a computer system comprising means for inputting a program to be protected, and for embedding at least one challenge means in that program, wherein the challenge means comprises means for
participating in a probabilistic proof protocol,
validating that the response means possesses the private keying material,
prohibiting a customer from using some or all of the program unless the validation succeeds.
According to a further aspect of the invention, there is provided a method of distributing software to a plurality of customers wherein each customer has a computer system having a protection mechanism for protecting software, the protection mechanism including at least one challenge means associated with a protected item of software, and at least one response means with private keying material that it can access, wherein: a) the challenge means has no access to the private keying material; b) the response means includes means for proving that it has access to the private keying material by interacting with the challenge means using a probabilistic proof scheme; c) the challenge means comprises means for prohibiting a customer from using some or all of said items of software unless the challenge means knows that the probabilistic proof is successful, and wherein every customer receives an identical copy of said protected program and of said challenge means.
According to a further aspect of the invention, there is provided a method for protecting an item of software, wherein at least one challenge means is associated with the protected item of software, and at least one response means accesses private keying material,
a) the challenge means has no access to the private keying material,
b) the response means proves that it has access to the private keying material by interacting with the challenge means using a probabilistic proof scheme, and
c) the challenge means prohibits a customer from using some or all of the items of software unless the challenge means knows that the probabilistic proof is successful.
According to a further aspect of the invention, it may be advantageous to generate random values by either the challenge means or the response means by repeatedly timing responses to device accesses in order to enforce the security of the random value. Although one may potentially time responses to any one of a variety of devices, in this present example we assume a disk (commonly known as a hard disk and sometimes known as a direct access storage device). Additionally, it is possible to query multiple different devices when generating one particular random value.
According to a further aspect of the invention, in order to further enforce the security of the random value one may, while generating the random value, fork new threads in such a manner as to introduce an additional degree of randomness into the random value by exploiting unpredictabilities in the operating system""s scheduler.
According to a further aspect of the invention, in order to further enforce the security of the random value one may perform a statistical test to determine the number of random bits obtained by each of the disk accesses, and cause disk accesses to be repeated until a predetermined number of random bits has been obtained.